package com.lw.leetcode.stack.b;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer 33. 二叉搜索树的后序遍历序列
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/6 17:07
 */
public class VerifyPostorder {

    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int limit = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            int v = postorder[i];
            if (v > limit) {
                return false;
            }
            while (!stack.isEmpty() && stack.peek() > v) {
                limit = stack.pop();
            }
            stack.add(v);
        }
        return true;
    }


    // 官方
    public boolean verifyPostorder2(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                root = stack.pop();
            }
            stack.add(postorder[i]);
        }
        return true;
    }


}
